package leetcode.weekly.week319;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

import leetcode.helper.H;
import leetcode.helper.tree.TreeNode;

//Solution3Test
public class Solution3 {

	public int minimumOperations(TreeNode root) {
		int ans = 0;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			ans += f(queue);
			int size = queue.size();
			while (size > 0) {
				TreeNode cur = queue.poll();
				if (cur.left != null) {
					queue.add(cur.left);
				}
				if (cur.right != null) {
					queue.add(cur.right);
				}
				size--;
			}
		}
		return ans;
	}

	private int f(Queue<TreeNode> queue) {
		TreeNode[] arr = queue.toArray(new TreeNode[] {});
		int[] nums = new int[arr.length];
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			nums[i] = arr[i].val;
			map.put(nums[i], i);
		}
		int[] ord = nums.clone();
		int ans = 0;
		Arrays.sort(ord);
		for (int i = 0; i < ord.length; i++) {
			int num = ord[i];
			if (map.get(num) == i) {
				continue;
			}
			int to = map.get(num);
			int num1 = nums[i];
			map.put(num1, to);
			nums[to] = num1;
			ans++;
		}
		return ans;
	}

}
